Va chạm băm nói chung không thể tránh khỏi khi băm một tập hợp ngẫu nhiên của một số lượng lớn các khóa. Ví dụ, nếu băm 2500 khóa vào một triệu ô nhớ, ngay cả với một phân bố hoàn toàn ngẫu nhiên, theo vấn đề sinh nhật có 95% cơ hội ít nhất hai trong số các khóa băm cùng một ô nhớ.

Vì vậy, hầu hết các thiết kế bảng băm đều có phương pháp giải quyết va chạm. Dưới đây là một số phương pháp phổ biến. Trong tất cả các phương pháp này, các khóa (hoặc con trỏ tới chúng) được lưu trữ trong bảng, cùng với các giá trị liên quan. Một điểm quan trọng là mức độ hiệu quả của các phương pháp giải quyết va chạm không phụ thuộc trực tiếp vào số lượng khóa n, mà vào hệ số tải (hay hệ số đầy) của bảng, tỷ lệ n/s giữa n và kích thước s của bảng.

Phương pháp kết nối

Trong phương pháp kết nối (còn gọi là kết nối riêng rẽ, kết nối trực tiếp), mỗi ô của bảng là một con trỏ tới một danh sách liên kết chứa các cặp khóa-giá trị được băm tới cùng một vị trí. Để tìm kiếm, thuật toán duyệt qua danh sách để tìm khóa cho trước. Để chèn khóa mới, thuật toán chèn khóa đó vào đầu danh sách ở ô nhớ tương ứng với giá trị băm của khóa. Để xóa một khóa, thuật toán phải duyệt qua danh sách và xóa khóa đó khỏi danh sách.

• Các nút bị băm cùng địa chỉ (các nút bị xung đột) được gom thành một danh sách liên kết.
• Các nút bị xung đột tại địa chỉ i được nối kết trực tiếp với nhau qua danh sách liên kết i.

Phương pháp địa chỉ mở

Trong phương pháp địa chỉ mở, mọi cặp khóa-giá trị được lưu trực tiếp trong bảng. Khi một cặp khóa-giá trị mới được chèn vào bảng, thuật toán duyệt trong bảng theo một thứ tự thăm dò nhất định bắt đầu từ ô tương ứng với giá trị băm của khóa, cho tới khi tìm được một ô trống. Cặp khóa-giá trị mới được chèn vào ô trống đó. Khi tìm kiếm, thuật toán cũng duyệt theo thứ tự thăm dò bắt đầu từ ô tương ứng với giá trị băm.

Một số thứ tự thăm dò phổ biến bao gồm:

• Thăm dò tuyến tính, trong đó khoảng cách giữa hai vị trí thăm dò liên tiếp là cố định (thường là 1)
• Thăm dò bậc hai, trong đó khoảng cách giữa hai vị trí thăm dò liên tiếp tăng dần tuyến tính
• Băm hai lần, trong đó khoảng cách giữa hai vị trí thăm dò liên tiếp là một hàm băm khác

Phương pháp băm Cuckoo

Phương pháp băm cuckoo (tên gọi xuất phát từ sự tương tự giữa hoạt động thuật toán với hành vi của chim Cuckoo) đảm bảo thời gian cho mỗi phép tìm kiếm là hằng số trong trường hợp xấu nhất, và thời gian trừ dần hằng số cho chèn và xóa.